← All Articles

[PROGRAMMERS] 추석 트래픽 - 2018 KAKAO BLIND

Posted on

문제 :

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.


입력 형식

  • solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
  • 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
  • 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
  • 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 “2016년 9월 15일 오전 3시 10분 33.010초“부터 “2016년 9월 15일 오전 3시 10분 33.020초“까지 ”0.011초” 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
  • 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
  • lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

  • solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.


풀이 :

쉽지 않은 문제이다. 구현양도 많을 뿐더러 처음부터 문자열은 어떻게 처리해서 시간단위로 변환할 것이고, 각 트래픽이 해당 1초 구간에 들어오는지 판별하기 위해 각 구간별 포지션 경우의 수를 잘 따져주어야 한다.

image

해당 1초 구간 내에 들어오는 트래픽 막대인 경우는 다음과 같이 3가지 경우의 수가 존재한다. 따라서 해당 3가지 경우의 수 중 하나라도 만족하는 막대만을 카운트해야 한다.


[ 세부 구현사항 ]

  1. 매개변수로 넘어오는 문자열 벡터 ‘lines’에서 구조체 TimeInfo 형으로 변환된 벡터인 vector<TimeInfo> timeLines 를 만들어 주는 과정을 첫 번째로 수행한다.
  2. 각 타임라인 별 시작 시간, 종료 시간을 모두 담은 오름차순 pq를 생성한다. => 종료시간은 기존 timelinse 정보를 사용하고 시작시간은 calculStartTime 함수를 활용하여 계산해준다.
  3. pq가 빌 때까지 loop를 돌면서 해당 시간에서 1초 구간(pq에 들어있는 시간부터 앞으로 1초 간의 구간, 시작 시간, 종료 시간이 다 포함되어 있기 때문에 각 타임라인이 걸쳐 있는 최대 갯수 구간을 파악할 수 있음)에 포함되는 최대 갯수를 파악할 수 있다.
  4. 각 구간에 포함된 타임라인 막대를 판단하는 경우에는 위 그림의 3가지 경우의 수 중 하나라도 포함되는지 판단한다.


코드 :

코드 보기/접기 
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct TimeInfo {
    int hour, minute;
    double second;
};

struct compare {
    bool operator()(TimeInfo a, TimeInfo b) {
        if (a.hour == b.hour) {
            if (a.minute == b.minute)
                return a.second > b.second;
            return a.minute > b.minute;
        }
        return a.hour > b.hour;
    }
};

TimeInfo stringToTimeInfo(string str) {
    return TimeInfo{
            stoi(str.substr(11, 2)),
            stoi(str.substr(14, 2)),
            stod(str.substr(17, 6)),
    };
}

double spliceProcessTime(string str) {
    string processStr = "";
    for (int k = 24;; k++) {
        if (str[k] == 's') break;
        processStr += str[k];
    }
    return stod(processStr);
}

TimeInfo calculStartTime(TimeInfo endInfo, double processTime) {
    TimeInfo startInfo = {endInfo.hour, endInfo.minute, endInfo.second};
    if ((startInfo.second -= processTime - 0.001) < 0) {
        startInfo.second += 60;
        if ((startInfo.minute -= 1) < 0) {
            startInfo.minute += 60;
            if ((startInfo.hour -= 1) < 0) return TimeInfo{0, 0, 0};
        }
    }

    return startInfo;
}

bool isGreaterEqualTime(TimeInfo a, TimeInfo b) {
    if (a.hour == b.hour) {
        if (a.minute == b.minute) return a.second >= b.second;
        return a.minute > b.minute;
    }
    return a.hour > b.hour;
}

bool isGreaterTime(TimeInfo a, TimeInfo b) {
    if (a.hour == b.hour) {
        if (a.minute == b.minute) return a.second > b.second;
        return a.minute > b.minute;
    }
    return a.hour > b.hour;
}

int solution(vector<string> lines) {
    priority_queue<TimeInfo, vector<TimeInfo>, compare> pq;
    vector<TimeInfo> timeLines, startTimeLines;
    int answer = 0;

    for (const string &str : lines)
        timeLines.push_back(stringToTimeInfo(str));

    for (int k = 0; k < lines.size(); k++) {
        double processTime = spliceProcessTime(lines[k]);
        TimeInfo startInfo = calculStartTime(timeLines[k], processTime);

        pq.push(startInfo);
        startTimeLines.push_back(startInfo);
        pq.push(timeLines[k]);
    }

    while (!pq.empty()) {
        TimeInfo endNorm = pq.top();
        pq.pop();
        TimeInfo startNorm = calculStartTime(endNorm, 1);
        int count = 0;

        for (int k = lines.size() - 1; k >= 0; k--) {
            TimeInfo endTime = timeLines[k], startTime = startTimeLines[k];
            if (isGreaterTime(startNorm, endTime)) break;
            if (
                    (isGreaterEqualTime(endTime, startNorm) && isGreaterEqualTime(endNorm, endTime)) ||
                    (isGreaterEqualTime(startTime, startNorm) && isGreaterEqualTime(endNorm, startTime)) ||
                    (isGreaterEqualTime(startNorm, startTime) && isGreaterEqualTime(endTime, endNorm))
                    )
                count++;
        }
        answer = max(answer, count);
    }

    return answer;
}


AlgorithmalgorithmprogrammersC++